from typing import *
from collections import deque

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        nexts = [[] for _ in range(n)]
        ins  = [0] * n
        for a,b in relations:
            nexts[a - 1].append(b - 1)
            ins[b - 1] += 1
        q = deque()
        for i in range(n):
            if ins[i] ==0 :
                q.append(i)
        s = [0] * n
        ans = 0
        while q:
            c = q.pop()
            s[c] += time[c]
            ans = max(ans,s[c])
            for nxt in nexts[c]:
                s[nxt] = max(s[nxt],s[c])
                ins[nxt]-=1
                if ins[nxt] ==0 :
                    q.append(nxt)
        return ans
            